Wannfly挑战赛19 B 矩阵

Posted on | In ,

给一个$R·C$的矩阵，问满足以下三个条件的最大子矩阵。
子矩阵不超过 $X$ 行。
子矩阵不超过 $Y$ 列。
子矩阵中 $0$ 的个数不能超过 $Z$ 个。
$(R,C,X,Y\le500，Z\le R·C)$

题解

  • 枚举符合条件的两行
  • 用剩下两个条件单调队列 列的范围
  • 时间复杂度 $O(R·C^2)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,m,c[505][505],X,Y,Z, a[505][505], lin[505][505], nowc[505], nowlin[505];
ll ans;

int main()
{
    scanf("%lld%lld%lld%lld%lld", &n,&m,&X,&Y,&Z);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++){
            scanf("%lld", &a[i][j]);
            c[i][j]=c[i-1][j]+a[i][j];
            lin[i][j]=lin[i-1][j]+(a[i][j]==0);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n&&(j-i+1)<=X;j++)
        {
            for(int k=1;k<=m;k++)
            {
                nowc[k]=c[j][k]-c[i-1][k]+nowc[k-1];
                nowlin[k]=lin[j][k]-lin[i-1][k]+nowlin[k-1];
            }
            deque<pair<ll,int>>q;
            q.push_back({0, 0});
            for(int l=1,r=1;r<=m;r++)
            {
                while(r-l+1>Y || nowlin[r]-nowlin[l-1]>Z) l++;
                while(!q.empty() && q.back().first>nowc[r]) q.pop_back();
                while(!q.empty() && q.front().second<l-1)q.pop_front();
                q.push_back({nowc[r], r});
                ans=max(ans, nowc[r]-q.front().first);
            }
        }
    }
    printf("%lld\n", ans);
}